Search Results

Documents authored by Cohen, Avi

Found 5 Possible Name Variants:

Cohen, David A.

Document
DOI: 10.4230/LIPIcs.STACS.2018.19
On Singleton Arc Consistency for CSPs Defined by Monotone Patterns

Authors: Clément Carbonnel, David A. Cohen, Martin C. Cooper, and Stanislav Zivny

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
Singleton arc consistency is an important type of local consistency which has been recently shown to solve all constraint satisfaction problems (CSPs) over constraint languages of bounded width. We aim to characterise all classes of CSPs defined by a forbidden pattern that are solved by singleton arc consistency and closed under removing constraints. We identify five new patterns whose absence ensures solvability by singleton arc consistency, four of which are provably maximal and three of which generalise 2-SAT. Combined with simple counter-examples for other patterns, we make significant progress towards a complete classification.
Cite as

Clément Carbonnel, David A. Cohen, Martin C. Cooper, and Stanislav Zivny. On Singleton Arc Consistency for CSPs Defined by Monotone Patterns. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{carbonnel_et_al:LIPIcs.STACS.2018.19,
  author =	{Carbonnel, Cl\'{e}ment and Cohen, David A. and Cooper, Martin C. and Zivny, Stanislav},
  title =	{{On Singleton Arc Consistency for CSPs Defined by Monotone Patterns}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{19:1--19:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.19},
  URN =		{urn:nbn:de:0030-drops-84876},
  doi =		{10.4230/LIPIcs.STACS.2018.19},
  annote =	{Keywords: constraint satisfaction problems, forbidden patterns, singleton arc consistency}
}

Cohen, Avi

Document
DOI: 10.4230/LIPIcs.MFCS.2021.32
Budgeted Dominating Sets in Uncertain Graphs

Authors: Keerti Choudhary, Avi Cohen, N. S. Narayanaswamy, David Peleg, and R. Vijayaragunathan

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
We study the Budgeted Dominating Set (BDS) problem on uncertain graphs, namely, graphs with a probability distribution p associated with the edges, such that an edge e exists in the graph with probability p(e). The input to the problem consists of a vertex-weighted uncertain graph 𝒢 = (V, E, p, ω) and an integer budget (or solution size) k, and the objective is to compute a vertex set S of size k that maximizes the expected total domination (or total weight) of vertices in the closed neighborhood of S. We refer to the problem as the Probabilistic Budgeted Dominating Set (PBDS) problem. In this article, we present the following results on the complexity of the PBDS problem. 1) We show that the PBDS problem is NP-complete even when restricted to uncertain trees of diameter at most four. This is in sharp contrast with the well-known fact that the BDS problem is solvable in polynomial time in trees. We further show that PBDS is 𝖶[1]-hard for the budget parameter k, and under the Exponential time hypothesis it cannot be solved in n^o(k) time. 2) We show that if one is willing to settle for (1-ε) approximation, then there exists a PTAS for PBDS on trees. Moreover, for the scenario of uniform edge-probabilities, the problem can be solved optimally in polynomial time. 3) We consider the parameterized complexity of the PBDS problem, and show that Uni-PBDS (where all edge probabilities are identical) is 𝖶[1]-hard for the parameter pathwidth. On the other hand, we show that it is FPT in the combined parameters of the budget k and the treewidth. 4) Finally, we extend some of our parameterized results to planar and apex-minor-free graphs. Our first hardness proof (Thm. 1) makes use of the new problem of k-Subset Σ-Π Maximization (k-SPM), which we believe is of independent interest. We prove its NP-hardness by a reduction from the well-known k-SUM problem, presenting a close relationship between the two problems.
Cite as

Keerti Choudhary, Avi Cohen, N. S. Narayanaswamy, David Peleg, and R. Vijayaragunathan. Budgeted Dominating Sets in Uncertain Graphs. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 32:1-32:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{choudhary_et_al:LIPIcs.MFCS.2021.32,
  author =	{Choudhary, Keerti and Cohen, Avi and Narayanaswamy, N. S. and Peleg, David and Vijayaragunathan, R.},
  title =	{{Budgeted Dominating Sets in Uncertain Graphs}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{32:1--32:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.32},
  URN =		{urn:nbn:de:0030-drops-144723},
  doi =		{10.4230/LIPIcs.MFCS.2021.32},
  annote =	{Keywords: Uncertain graphs, Dominating set, NP-hard, PTAS, treewidth, planar graph}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.10
Minimum Neighboring Degree Realization in Graphs and Trees

Authors: Amotz Bar-Noy, Keerti Choudhary, Avi Cohen, David Peleg, and Dror Rawitz

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
We study a graph realization problem that pertains to degrees in vertex neighborhoods. The classical problem of degree sequence realizability asks whether or not a given sequence of n positive integers is equal to the degree sequence of some n-vertex undirected simple graph. While the realizability problem of degree sequences has been well studied for different classes of graphs, there has been relatively little work concerning the realizability of other types of information profiles, such as the vertex neighborhood profiles. In this paper we introduce and explore the minimum degrees in vertex neighborhood profile as it is one of the most natural extensions of the classical degree profile to vertex neighboring degree profiles. Given a graph G = (V,E), the min-degree of a vertex v ∈ V, namely MinND(v), is given by min{deg(w) ∣ w ∈ N[v]}. Our input is a sequence σ = (d_𝓁^{n_𝓁}, ⋯ , d₁^{n₁}), where d_{i+1} > d_i and each n_i is a positive integer. We provide some necessary and sufficient conditions for σ to be realizable. Furthermore, under the restriction that the realization is acyclic, i.e., a tree or a forest, we provide a full characterization of realizable sequences, along with a corresponding constructive algorithm. We believe our results are a crucial step towards understanding extremal neighborhood degree relations in graphs.
Cite as

Amotz Bar-Noy, Keerti Choudhary, Avi Cohen, David Peleg, and Dror Rawitz. Minimum Neighboring Degree Realization in Graphs and Trees. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.ESA.2020.10,
  author =	{Bar-Noy, Amotz and Choudhary, Keerti and Cohen, Avi and Peleg, David and Rawitz, Dror},
  title =	{{Minimum Neighboring Degree Realization in Graphs and Trees}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.10},
  URN =		{urn:nbn:de:0030-drops-128765},
  doi =		{10.4230/LIPIcs.ESA.2020.10},
  annote =	{Keywords: Graph realization, neighborhood profile, graph algorithms, degree sequences}
}

Cohen, Avihay

Document
DOI: 10.4230/OASIcs.CMN.2014.42
Towards Empathic Neurofeedback for Interactive Storytelling

Authors: Marc Cavazza, Gabor Aranyi, Fred Charles, Julie Porteous, Stephen Gilroy, Ilana Klovatch, Gilan Jackont, Eyal Soreq, Nimrod Jakob Keynan, Avihay Cohen, Gal Raz, and Talma Hendler

Published in: OASIcs, Volume 41, 2014 Workshop on Computational Models of Narrative

Abstract
Interactive Narrative is a form of digital entertainment based on AI techniques which support narrative generation and user interaction. Despite recent progress in the field, there is still a lack of unified models integrating narrative generation, user response and interaction. This paper addresses this issue by revisiting existing Interactive Narrative paradigms, granting explicit status to users' disposition towards story characters. We introduce a novel Brain-Computer Interface (BCI) design, which attempts to capture empathy for the main character in a way that is compatible with filmic theories of emotion. Results from two experimental studies with a fully-implemented system demonstrate the effectiveness of a neurofeedback-based approach, showing that subjects can successfully modulate their emotional support for a character who is confronted with challenging situations. A preliminary fMRI analysis also shows activation during user interaction, in regions of the brain associated with emotional control.
Cite as

Marc Cavazza, Gabor Aranyi, Fred Charles, Julie Porteous, Stephen Gilroy, Ilana Klovatch, Gilan Jackont, Eyal Soreq, Nimrod Jakob Keynan, Avihay Cohen, Gal Raz, and Talma Hendler. Towards Empathic Neurofeedback for Interactive Storytelling. In 2014 Workshop on Computational Models of Narrative. Open Access Series in Informatics (OASIcs), Volume 41, pp. 42-60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{cavazza_et_al:OASIcs.CMN.2014.42,
  author =	{Cavazza, Marc and Aranyi, Gabor and Charles, Fred and Porteous, Julie and Gilroy, Stephen and Klovatch, Ilana and Jackont, Gilan and Soreq, Eyal and Keynan, Nimrod Jakob and Cohen, Avihay and Raz, Gal and Hendler, Talma},
  title =	{{Towards Empathic Neurofeedback for Interactive Storytelling}},
  booktitle =	{2014 Workshop on Computational Models of Narrative},
  pages =	{42--60},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-71-2},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{41},
  editor =	{Finlayson, Mark A. and Meister, Jan Christoph and Bruneau, Emile G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2014.42},
  URN =		{urn:nbn:de:0030-drops-46442},
  doi =		{10.4230/OASIcs.CMN.2014.42},
  annote =	{Keywords: brain-computer interfaces, neurofeedback, interactive narrative, affective computing}
}

Cohen, David

Document
DOI: 10.4230/DagSemProc.06401.3
A Unifying Theory of Structural Decompostions for the Constraint Satisfaction Problems

Authors: David Cohen, Marc Gyssens, and Peter Jeavons

Published in: Dagstuhl Seminar Proceedings, Volume 6401, Complexity of Constraints (2006)

Abstract
In this talk (draft paper) we develop the theory of structural decompositions for the CSP. We begin with the very general notion of a guarded decomposition and make several simplifying assumptions to arrive a the definition of an acyclic guarded cover. We show how many existing decompositions can seen as acyclic guarded covers. We develop a generic algorithm for discovering acyclic guarded covers under the further assumption that they have a join tree satisfying a simple extra condition. We show that many existing decompositions do in fact satisfy this extra condition. Using this theory we are able to describe a new class of structural decompostion which we call spread cuts. These generalise many existing decomposition methods. We present a class of hypergraphs whose spread cut width is significantly smaller than their hypertree width. The definition of a guarded decomposition and the algorithm for discovering them were motvated by the similar algorithms developed by Gottlob, Scarcello and Leone in their work on hypertrees. The authors also wish to acknowledge that an acyclic guarded decomposition is very similar to a generalised hypertree decomposition as described in the hypertree literature.
Cite as

David Cohen, Marc Gyssens, and Peter Jeavons. A Unifying Theory of Structural Decompostions for the Constraint Satisfaction Problems. In Complexity of Constraints. Dagstuhl Seminar Proceedings, Volume 6401, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:DagSemProc.06401.3,
  author =	{Cohen, David and Gyssens, Marc and Jeavons, Peter},
  title =	{{A Unifying Theory of Structural Decompostions for the Constraint Satisfaction Problems}},
  booktitle =	{Complexity of Constraints},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6401},
  editor =	{Nadia Creignou and Phokion Kolaitis and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06401.3},
  URN =		{urn:nbn:de:0030-drops-8017},
  doi =		{10.4230/DagSemProc.06401.3},
  annote =	{Keywords: Structural decomposition, spread cut}
}

Cohen, Ravid

Document
DOI: 10.4230/LIPIcs.SoCG.2019.26
Maintaining the Union of Unit Discs Under Insertions with Near-Optimal Overhead

Authors: Pankaj K. Agarwal, Ravid Cohen, Dan Halperin, and Wolfgang Mulzer

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
We present efficient data structures for problems on unit discs and arcs of their boundary in the plane. (i) We give an output-sensitive algorithm for the dynamic maintenance of the union of n unit discs under insertions in O(k log^2 n) update time and O(n) space, where k is the combinatorial complexity of the structural change in the union due to the insertion of the new disc. (ii) As part of the solution of (i) we devise a fully dynamic data structure for the maintenance of lower envelopes of pseudo-lines, which we believe is of independent interest. The structure has O(log^2 n) update time and O(log n) vertical ray shooting query time. To achieve this performance, we devise a new algorithm for finding the intersection between two lower envelopes of pseudo-lines in O(log n) time, using tentative binary search; the lower envelopes are special in that at x=-infty any pseudo-line contributing to the first envelope lies below every pseudo-line contributing to the second envelope. (iii) We also present a dynamic range searching structure for a set of circular arcs of unit radius (not necessarily on the boundary of the union of the corresponding discs), where the ranges are unit discs, with O(n log n) preprocessing time, O(n^{1/2+epsilon} + l) query time and O(log^2 n) amortized update time, where l is the size of the output and for any epsilon>0. The structure requires O(n) storage space.
Cite as

Pankaj K. Agarwal, Ravid Cohen, Dan Halperin, and Wolfgang Mulzer. Maintaining the Union of Unit Discs Under Insertions with Near-Optimal Overhead. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2019.26,
  author =	{Agarwal, Pankaj K. and Cohen, Ravid and Halperin, Dan and Mulzer, Wolfgang},
  title =	{{Maintaining the Union of Unit Discs Under Insertions with Near-Optimal Overhead}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.26},
  URN =		{urn:nbn:de:0030-drops-104307},
  doi =		{10.4230/LIPIcs.SoCG.2019.26},
  annote =	{Keywords: lower envelopes, pseudo-lines, unit discs, range search, dynamic algorithms, tentative binary search}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact